package train.DAT622;

import java.util.ArrayList;
import java.util.List;

public class LeetCode622 {
    public static void main(String[] args) {
//        List<List<Integer>> lists = yanHui(4);
//        for (List<Integer> list : lists) {
//            System.out.println("list = " + list);
//        }
//        int[][] ints = yanHui2(4);
//        for (int[] anInt : ints) {
//            for (int i : anInt) {
//                System.out.print(i+"\t");
//            }
//            System.out.println();
//        int[] a={1,-2,4,8,-4,7,-1,-5};
//        System.out.println(langShu(a));

//        int [] nums1={2,4};
//        int[] nums2={1,2,3,4};
//        int[] ints = nextGreater(nums1, nums2);
//        for (int anInt : ints) {
//            System.out.println("anInt = " + anInt);
//        }
//螺旋的
//       int[][] a={{1,2,3},{4,5,6},{7,8,9}};
//        int[] ints = spirOrder(a);
//        for (int anInt : ints) {
//            System.out.println("anInt = " + anInt);
//        }

        int[] a={1,2,3,1,2,3};
        System.out.println(conNear(a, 2));


    }

    //杨辉三角
    public static List<List<Integer>> yanHui(int n){
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> list1 = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            List<Integer> temp=new ArrayList<>();
            int[] a=new int[i-1];
            for (int j = 0; j < list1.size(); j++) {
                a[j]=list1.get(j);
            }
            list1.clear();
            
            if(i==1) {
                list1.add(1);
            }else if(i==2){
                list1.add(1);
                list1.add(1);
             } else{
                list1.add(1);
                for (int j = 1; j < a.length; j++) {
                    list1.add(a[j]+a[j-1]);
                }
                list1.add(1);
                
            }
            for (int j = 0; j < list1.size(); j++) {
                temp.add(list1.get(j));
            }
            list.add(temp);
        }
        return list;
    }
    //杨辉三角数组类型2
    public static int[][] yanHui2(int n) {
        int[][] a = new int[n][];
        for (int j = 0; j < n; j++) {
            if (j == 0) {
                a[0] = new int[1];
                a[0][0] = 1;
            } else if (j == 1) {
                a[1] = new int[2];
                a[1][0] = 1;
                a[1][1] = 1;
            } else {
                a[j] = new int[j+1];
                a[j][0] = 1;
                for (int i = 1; i < a[j].length - 1; i++)
                    a[j][i] = a[j-1][i - 1] + a[j-1][i];

                a[j][j] = 1;

            }

        } return a;
    }

    //最长连续子数组
    public static int langShu(int[] nums){
        int sum=nums[0];
        int max=nums[0];
        int a=0,b=0;
        for (int i = 1; i < nums.length; i++) {
            sum+=nums[i];
            if(sum<nums[i]){
                sum=nums[i];
            }
            if(max<=sum) max=sum;

        }
        return max;
    }

    //下一个更大元素I
    public static int[] nextGreater(int[] nums1,int[] nums2){
        int[] a=new int[nums1.length];
        int k=0;
        for (int i = 0; i < nums1.length; i++) {
            if(nums1[i]==nums2[nums2.length-1]) {
                a[i]=-1;
                continue;
            }
            for (int j = 0; j < nums2.length-1; j++) {
                if(nums1[i]==nums2[j]) {
                    for ( k = j; k < nums2.length ; k++) {
                          if(nums2[k]>nums1[i]) {
                              a[i]=nums2[k];
                              break;
                          }
                    }
                    if(k== nums2.length) a[i]=-1;
                }
            }
        }
        return a;
    }

    //是否在一条直线上
    public static boolean checkStr(int[][] coordinates){
        int x=coordinates[1][0]-coordinates[0][0];
        int y=coordinates[1][1]-coordinates[0][1];
        if(coordinates.length<=2)
            return true;
        for (int i = 2; i <coordinates.length ; i++) {
            int a=coordinates[i][0]-coordinates[0][0];
            int b=coordinates[i][1]-coordinates[0][1];
            if(a*y!=b*x)
                return false;
        }
        return true;
    }
    //螺旋矩阵 网上的思路
    public static int[] spirOrder(int[][] matrix){
       int[] a=new int[matrix[0].length*matrix.length];
       int i=0,k=0;
       int left=0,right=matrix[0].length-1,up=0,down= matrix.length-1;
        while(left<=right&&up<=down) {
            for (int j = left; j <= right; j++) {
                a[k] = matrix[up][j];
                k++;
            }
            for (int j = up+1; j <=down ; j++) {
                a[k]=matrix[j][right];
                k++;
            }
            if(left<right&&up<down) {
                for (int j = right - 1; j > left; j--) {
                    a[k] = matrix[down][j];
                    k++;
                }
                for (int j = down; j > up; j--) {
                    a[k] = matrix[j][left];
                    k++;
                }
            }
            left++;
            right--;
            up++;
            down--;
        }

return  a;






       /////////'''''''''''''''''''''
//       int i=0,j=0;
//       int up=0;//遇见左向上走1
//        int down=0;//遇见右向下走；2
//        int left=0;//遇见下向左走3
//        int right=0;//遇见上向右走4
//        int x= matrix.length;//几行
//        int y=matrix[0].length;//几列
//        int c=0,d=0;//c表示第几行，d表示第几列
//        int k=0;//第几个数
//        boolean flag=true;
//        for ( i = 0; i < matrix[0].length* matrix.length; i++) {
//            if(flag){
//                for(j=0;j<y;j++){
//                    a[k]=matrix[c][j];
//                    d=j;
//                    k++;
//                    i++;
//
//                }
//                c++;
//                x--;
//                if(d+1==y) down=2;
//                flag=false;
//            }
//            if(down==2){
//                for(j=c;j<=x;j++){
//                    a[k]=matrix[j][d];
//                    i++;
//                    c=j;
//                    k++;
//                }
//                y--;
//                d--;
//              left=3;
//
//            }
//            if(left==3){
//                for(j=d;d>=0;j--){
//                   a[k]=matrix[c][j];
//                   k++;
//                   i++;
//                   d=j;
//                }
//                up=1;
//                x--;
//                c--;
//            }
//            if(up==1){
//
//            }
//
//        }
//       return a;
    }


    //验证回文字符串
    public static boolean isPal(String s){
        StringBuffer buffer = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i)>='a'&&s.charAt(i)<='z') buffer.append(s.charAt(i));
            if(s.charAt(i)>='A'&&s.charAt(i)<='Z') buffer.append((char)(s.charAt(i)+32));
            if(s.charAt(i)>='0'&&s.charAt(i)<='9') buffer.append(s.charAt(i));
        }
        System.out.println(buffer.toString());
        for (int i = 0; i < buffer.length()/2; i++) {
            if(buffer.charAt(i)!= buffer.charAt(buffer.length()-i-1)) return false;
        }
        return true;
    }

    //存在重复元素
    public static boolean conNear(int[] nums,int k){
       int temp=0;
        for (int i = 0; i < nums.length-k; i++) {
            for (int j = 1; j <= k ; j++) {
                if(nums[i]==nums[i+j]){
                    return true;
                }

            }
        }
        for (int i = nums.length-k; i < nums.length-1; i++) {
            for (int j = i+1; j < nums.length ; j++) {
                if(nums[i]==nums[j]) return true;
            }
        }
        if(nums.length<=k){
            for (int i = 0; i < nums.length-1; i++) {
                for (int j = i+1; j < nums.length ; j++) {
                    if(nums[i]==nums[j]) return true;
                }

            }
        }
        return false;
    }

    //汇总区间


}
